import org.junit.Test;

import java.util.*;

public class Solution {




    @Test
    public void levelOrder() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        List<List<Integer>> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null){
            queue.add(root);
        }
        int layers = 1;
        while(!queue.isEmpty()){
            List<Integer> arr = new ArrayList<>();
            if(layers%2==1){
                for (int i = queue.size(); i > 0; i--) {
                    TreeNode cur = queue.poll();
                    arr.add(cur.val);
                    if(cur.left!=null)queue.add(cur.left);
                    if(cur.right!=null)queue.add(cur.right);
                }
            }else {
                for (int i = 0; i > queue.size(); i++) {
                    TreeNode cur = queue.poll();
                    arr.add(cur.val);
                    if(cur.left!=null)queue.add(cur.left);
                    if(cur.right!=null)queue.add(cur.right);
                }
            }
            list.add(arr);
            layers++;
        }
        System.out.println(list);
    }

    void layer_l(TreeNode root, List<Integer> arr, Queue<TreeNode> queue){
        for (int i = queue.size(); i > 0; i--) {
            root = queue.poll();
            arr.add(root.val);
            if(root.left!=null)queue.add(root.left);
            if(root.right!=null)queue.add(root.right);
        }
    }
    void layer_r(TreeNode root, List<Integer> arr, Queue<TreeNode> queue){
        for (int i = queue.size(); i > 0; i--) {
            root = queue.poll();
            arr.add(root.val);
            if(root.right!=null)queue.add(root.right);
            if(root.left!=null)queue.add(root.left);
        }
    }


    void TreeOrder(TreeNode root, List<Integer> arr, List<List<Integer>> list) {

        if(root.left == null||root.right == null){
            return;
        }
        arr.add(root.left.val);
        arr.add(root.right.val);
        list.add(new LinkedList<>(arr));
        arr.clear();
        System.out.println(list);
        TreeOrder(root.left, arr, list);
        TreeOrder(root.right, arr, list);

    }

    @Test
    public void reverseList() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(2);
        reverseList1(head);

    }
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList1(head.next);

        head.next.next = head;

        head.next = null;

        return newHead;

    }


/*
* 贪心算法
* 每次都认为可行的局部解
* 如果不行，遍历
* 直到return false
* */
    @Test
    public void wordBreak(  ) {
//        String s = "catsandog";
//        List<String> wordDict = new LinkedList<>();
//        wordDict.add("cats");
//        wordDict.add("dog");
//        wordDict.add("sand");
//        wordDict.add("and");
//        wordDict.add("cat");
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordDict.add("code");
        System.out.println(wordDict);
        int len = s.length();
        int list_len = wordDict.size();
        Set<String> wordDictSet = new HashSet(wordDict);
        System.out.println(wordDictSet);
//        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
//        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        System.out.println(dp[s.length()]);

    }



    @Test
    public void wordBrea1k(  ) {
        String s = "leetcode";
        List<String> wordDict = new LinkedList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordDict.add("code");
        System.out.println(wordDict);
        int len = s.length();
        int list_len = wordDict.size();
        Set<String> wordDictSet = new HashSet(wordDict);
        System.out.println(wordDictSet);
        Boolean[] result = new Boolean[len+1];
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (wordDict.contains(s.substring(j,i) )){
                    result[i] = true;
                    break;
                }
            }
        }
        String r = Arrays.toString(result);
        System.out.println(r);


    }

    @Test
    public void word2Break(  ) {
        String s = "leetcode";

        for (int i = 0; i <= s.length(); i++) {
//            System.out.print(s.charAt(i));
            System.out.println("第"+i+"th = " + s.substring(0,i));
        }


    }

    @Test
    public void mergeTwoLists1() {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(6);
        List<Integer> ll = new ArrayList<>();
        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(5);
        ListNode l3 = mergeTwoLists(l1,l2);
        while(l3!=null){
            ll.add(l3.val);
            l3 = l3.next;
        }
        System.out.println(ll);


    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null) {
            System.out.println(l2.val);
            return l2;
        } else if (l2 == null) {
            System.out.println(l1.val);
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            System.out.println(l1.val);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            System.out.println(l2.val);
            return l2;
        }
//        System.out.println();
    }






}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return super.toString();
    }
}

 class TreeNode {
    int val;
   TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
